/**
 * @Project : AlgorithmLearning
 * @Package : ACWing._2LanQiao._8numberTheory
 * @File : Template.java
 * @Author : WangRuoyu
 * @Date 2023/3/20 22:59
 */

package acwing._2LanQiao._8NumberTheory;

/**
 * @Project : AlgorithmLearning
 * @Package : ACWing._2LanQiao._8numberTheory
 * @File : Template.java
 * @Author : WangRuoyu
 * @Date 2023/3/20 22:59
 */

public class Template {
    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    // 筛质数 O(n)的时间找出所有质数
    static int[] primes = new int[10000];// 存储所有质数
    static boolean[] st = new boolean[10000]; // 判断当前数有没有被筛过
    static int cnt = 0;

    static void getPrimes(int n) {
        for (int i = 2; i <= n; ++i) {
            if (!st[i]) primes[cnt++] = i;
            for (int j = 0; primes[j] * i <= n; ++j) {
                st[primes[j] * i] = true;
                if (i % primes[j] == 0) break;
            }
        }
    }

    static int exgcd(int a, int b, int[] x, int[] y) { // java 无法传递引用，因此使用数组来记录传出的值
        if (b == 0) {
            x[0] = 1;
            y[0] = 0;
            return a;
        } else {
            int d = exgcd(b, a % b, y, x);
            y[0] -= a / b * x[0];
            return d;
        }
    }


    public static void main(String[] args) {
        int a = 12;
        int b = 16;
        int[] x = {0};
        int[] y = {0};
        int d = exgcd(a, b, x, y);
        System.out.println(a + "*" + x[0] + "+" + b + "*" + y[0] + "=" + d);
    }
}

